package com.yiwenup.leetcode.offer;

import com.yiwenup.leetcode.TreeNode;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.StringJoiner;

/**
 * https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
 * 执行用时：17 ms, 在所有 Java 提交中击败了64.31%的用户
 * 内存消耗：40.8 MB, 在所有 Java 提交中击败了32.08%的用户
 **/
public class No037 {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringJoiner joiner = new StringJoiner(",");

        // 层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null)  queue.offer(root);

        if (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                joiner.add(String.valueOf(node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                joiner.add("null");
            }
        }

        return joiner.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;

        TreeNode root;
        String[] vals = data.split(",");
        root = new TreeNode(Integer.parseInt(vals[0]));

        // 层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int step = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (!Objects.equals(vals[step], "null")) {
                node.left = new TreeNode(Integer.parseInt(vals[step]));
                queue.offer(node.left);
            }
            step++;

            if (!Objects.equals(vals[step], "null")) {
                node.right = new TreeNode(Integer.parseInt(vals[step]));
                queue.offer(node.right);
            }
            step++;
        }

        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));